DAY 15 試題

問題描述

在這個問題中，我們需要設計一個算法來將一個字串列表編碼為單個字串，並能夠透過網路傳送該編碼後的字串，再解碼回原始的字串列表。這意味著我們需要兩個函數：

1. encode：將字串列表轉換成一個可以透過網路傳輸的單個字串。
2. decode：接收該單個字串，並將其還原為字串列表。

需要注意的是，字串中可能包含任何可能的 ASCII 字元，因此我們的編碼方式必須能夠處理各種情況。此外，我們不能使用現有的序列化方法或依賴全局狀態，算法應該是無狀態的。

解題思路

這題的核心問題是如何將多個字串編碼成一個字串，並確保編碼後的字串能夠正確地解碼回來。為了解決這個問題，我們可以使用一種通用的編碼方式，即將每個字串的長度加到字串前面，這樣解碼時可以根據長度還原字串。

具體步驟如下：

1. 編碼 (Encode)：對於每個字串，將其長度轉換成字串，然後在該長度後面加上一個特殊的分隔符（例如 #），接著加上原始字串。如此處理所有字串，並將這些部分拼接成一個完整的編碼字串。

例如：如果有兩個字串 ["leet", "code"]，我們可以將其編碼為 4#leet4#code，其中 4# 表示長度為 4 的字串，後面的部分為實際的字串內容。
2. 解碼 (Decode)：接收到編碼字串後，我們需要遍歷該字串，找到分隔符 #，並根據前面的數字確定字串的長度，然後提取該字串。重複此操作直到還原整個列表。

這樣的設計確保了任意字串中的字元不會干擾編碼過程，並且能夠正確地解碼回原始字串列表。

class Solution {
public:
    // 將字串列表編碼為單一字串
    string encode(vector<string>& strs) {
        string encoded = "";
        for (const string& str : strs) {
            encoded += to_string(str.size()) + "#" + str;
        }
        return encoded;
    }

    // 將單一字串解碼為字串列表
    vector<string> decode(const string& s) {
        vector<string> result;
        int i = 0;
        while (i < s.size()) {
            // 找到分隔符 #
            int j = i;
            while (s[j] != '#') j++;
            // 取得長度
            int len = stoi(s.substr(i, j - i));
            // 取得實際字串
            result.push_back(s.substr(j + 1, len));
            // 更新索引，指向下一個字串
            i = j + 1 + len;
        }
        return result;
    }
};

解法重點與分析

重點在於如何有效地將字串編碼與解碼。藉由在每個字串前加上其長度與特殊分隔符 #，我們能夠避免字串中出現的任何字符干擾編碼格式。編碼過程需要將每個字串的長度轉換為字串並加上實際字串內容，而解碼過程則需要解析長度並根據該長度來切分字串。

這樣的編碼方式既簡單又通用，且不依賴於任何特殊函數或資料結構，完全符合問題的要求。

總結

這個編碼與解碼的問題通過在每個字串前添加其長度與特殊分隔符來實現。我們將問題簡化為如何區分字串與字串長度，並通過遍歷與分割來還原字串列表。這種方式有效且簡潔，編碼與解碼的時間複雜度均為 O(n)，其中 n 是所有字串長度的總和，空間複雜度也為 O(n)。

以上是第十五天的自學內容分享，謝謝大家。